home *** CD-ROM | disk | FTP | other *** search
/ Chip 2007 January, February, March & April / Chip-Cover-CD-2007-02.iso / Pakiet bezpieczenstwa / mini Pentoo LiveCD 2006.1 / mpentoo-2006.1.iso / livecd.squashfs / usr / lib / python2.4 / difflib.pyc (.txt) < prev    next >
Python Compiled Bytecode  |  2005-10-18  |  61KB  |  1,781 lines

  1. # Source Generated with Decompyle++
  2. # File: in.pyc (Python 2.4)
  3.  
  4. '''
  5. Module difflib -- helpers for computing deltas between objects.
  6.  
  7. Function get_close_matches(word, possibilities, n=3, cutoff=0.6):
  8.     Use SequenceMatcher to return list of the best "good enough" matches.
  9.  
  10. Function context_diff(a, b):
  11.     For two lists of strings, return a delta in context diff format.
  12.  
  13. Function ndiff(a, b):
  14.     Return a delta: the difference between `a` and `b` (lists of strings).
  15.  
  16. Function restore(delta, which):
  17.     Return one of the two sequences that generated an ndiff delta.
  18.  
  19. Function unified_diff(a, b):
  20.     For two lists of strings, return a delta in unified diff format.
  21.  
  22. Class SequenceMatcher:
  23.     A flexible class for comparing pairs of sequences of any type.
  24.  
  25. Class Differ:
  26.     For producing human-readable deltas from sequences of lines of text.
  27.  
  28. Class HtmlDiff:
  29.     For producing HTML side by side comparison with change highlights.
  30. '''
  31. __all__ = [
  32.     'get_close_matches',
  33.     'ndiff',
  34.     'restore',
  35.     'SequenceMatcher',
  36.     'Differ',
  37.     'IS_CHARACTER_JUNK',
  38.     'IS_LINE_JUNK',
  39.     'context_diff',
  40.     'unified_diff',
  41.     'HtmlDiff']
  42. import heapq
  43.  
  44. def _calculate_ratio(matches, length):
  45.     if length:
  46.         return 2.0 * matches / length
  47.     
  48.     return 1.0
  49.  
  50.  
  51. class SequenceMatcher:
  52.     '''
  53.     SequenceMatcher is a flexible class for comparing pairs of sequences of
  54.     any type, so long as the sequence elements are hashable.  The basic
  55.     algorithm predates, and is a little fancier than, an algorithm
  56.     published in the late 1980\'s by Ratcliff and Obershelp under the
  57.     hyperbolic name "gestalt pattern matching".  The basic idea is to find
  58.     the longest contiguous matching subsequence that contains no "junk"
  59.     elements (R-O doesn\'t address junk).  The same idea is then applied
  60.     recursively to the pieces of the sequences to the left and to the right
  61.     of the matching subsequence.  This does not yield minimal edit
  62.     sequences, but does tend to yield matches that "look right" to people.
  63.  
  64.     SequenceMatcher tries to compute a "human-friendly diff" between two
  65.     sequences.  Unlike e.g. UNIX(tm) diff, the fundamental notion is the
  66.     longest *contiguous* & junk-free matching subsequence.  That\'s what
  67.     catches peoples\' eyes.  The Windows(tm) windiff has another interesting
  68.     notion, pairing up elements that appear uniquely in each sequence.
  69.     That, and the method here, appear to yield more intuitive difference
  70.     reports than does diff.  This method appears to be the least vulnerable
  71.     to synching up on blocks of "junk lines", though (like blank lines in
  72.     ordinary text files, or maybe "<P>" lines in HTML files).  That may be
  73.     because this is the only method of the 3 that has a *concept* of
  74.     "junk" <wink>.
  75.  
  76.     Example, comparing two strings, and considering blanks to be "junk":
  77.  
  78.     >>> s = SequenceMatcher(lambda x: x == " ",
  79.     ...                     "private Thread currentThread;",
  80.     ...                     "private volatile Thread currentThread;")
  81.     >>>
  82.  
  83.     .ratio() returns a float in [0, 1], measuring the "similarity" of the
  84.     sequences.  As a rule of thumb, a .ratio() value over 0.6 means the
  85.     sequences are close matches:
  86.  
  87.     >>> print round(s.ratio(), 3)
  88.     0.866
  89.     >>>
  90.  
  91.     If you\'re only interested in where the sequences match,
  92.     .get_matching_blocks() is handy:
  93.  
  94.     >>> for block in s.get_matching_blocks():
  95.     ...     print "a[%d] and b[%d] match for %d elements" % block
  96.     a[0] and b[0] match for 8 elements
  97.     a[8] and b[17] match for 6 elements
  98.     a[14] and b[23] match for 15 elements
  99.     a[29] and b[38] match for 0 elements
  100.  
  101.     Note that the last tuple returned by .get_matching_blocks() is always a
  102.     dummy, (len(a), len(b), 0), and this is the only case in which the last
  103.     tuple element (number of elements matched) is 0.
  104.  
  105.     If you want to know how to change the first sequence into the second,
  106.     use .get_opcodes():
  107.  
  108.     >>> for opcode in s.get_opcodes():
  109.     ...     print "%6s a[%d:%d] b[%d:%d]" % opcode
  110.      equal a[0:8] b[0:8]
  111.     insert a[8:8] b[8:17]
  112.      equal a[8:14] b[17:23]
  113.      equal a[14:29] b[23:38]
  114.  
  115.     See the Differ class for a fancy human-friendly file differencer, which
  116.     uses SequenceMatcher both to compare sequences of lines, and to compare
  117.     sequences of characters within similar (near-matching) lines.
  118.  
  119.     See also function get_close_matches() in this module, which shows how
  120.     simple code building on SequenceMatcher can be used to do useful work.
  121.  
  122.     Timing:  Basic R-O is cubic time worst case and quadratic time expected
  123.     case.  SequenceMatcher is quadratic time for the worst case and has
  124.     expected-case behavior dependent in a complicated way on how many
  125.     elements the sequences have in common; best case time is linear.
  126.  
  127.     Methods:
  128.  
  129.     __init__(isjunk=None, a=\'\', b=\'\')
  130.         Construct a SequenceMatcher.
  131.  
  132.     set_seqs(a, b)
  133.         Set the two sequences to be compared.
  134.  
  135.     set_seq1(a)
  136.         Set the first sequence to be compared.
  137.  
  138.     set_seq2(b)
  139.         Set the second sequence to be compared.
  140.  
  141.     find_longest_match(alo, ahi, blo, bhi)
  142.         Find longest matching block in a[alo:ahi] and b[blo:bhi].
  143.  
  144.     get_matching_blocks()
  145.         Return list of triples describing matching subsequences.
  146.  
  147.     get_opcodes()
  148.         Return list of 5-tuples describing how to turn a into b.
  149.  
  150.     ratio()
  151.         Return a measure of the sequences\' similarity (float in [0,1]).
  152.  
  153.     quick_ratio()
  154.         Return an upper bound on .ratio() relatively quickly.
  155.  
  156.     real_quick_ratio()
  157.         Return an upper bound on ratio() very quickly.
  158.     '''
  159.     
  160.     def __init__(self, isjunk = None, a = '', b = ''):
  161.         '''Construct a SequenceMatcher.
  162.  
  163.         Optional arg isjunk is None (the default), or a one-argument
  164.         function that takes a sequence element and returns true iff the
  165.         element is junk.  None is equivalent to passing "lambda x: 0", i.e.
  166.         no elements are considered to be junk.  For example, pass
  167.             lambda x: x in " \\t"
  168.         if you\'re comparing lines as sequences of characters, and don\'t
  169.         want to synch up on blanks or hard tabs.
  170.  
  171.         Optional arg a is the first of two sequences to be compared.  By
  172.         default, an empty string.  The elements of a must be hashable.  See
  173.         also .set_seqs() and .set_seq1().
  174.  
  175.         Optional arg b is the second of two sequences to be compared.  By
  176.         default, an empty string.  The elements of b must be hashable. See
  177.         also .set_seqs() and .set_seq2().
  178.         '''
  179.         self.isjunk = isjunk
  180.         self.a = None
  181.         self.b = None
  182.         self.set_seqs(a, b)
  183.  
  184.     
  185.     def set_seqs(self, a, b):
  186.         '''Set the two sequences to be compared.
  187.  
  188.         >>> s = SequenceMatcher()
  189.         >>> s.set_seqs("abcd", "bcde")
  190.         >>> s.ratio()
  191.         0.75
  192.         '''
  193.         self.set_seq1(a)
  194.         self.set_seq2(b)
  195.  
  196.     
  197.     def set_seq1(self, a):
  198.         '''Set the first sequence to be compared.
  199.  
  200.         The second sequence to be compared is not changed.
  201.  
  202.         >>> s = SequenceMatcher(None, "abcd", "bcde")
  203.         >>> s.ratio()
  204.         0.75
  205.         >>> s.set_seq1("bcde")
  206.         >>> s.ratio()
  207.         1.0
  208.         >>>
  209.  
  210.         SequenceMatcher computes and caches detailed information about the
  211.         second sequence, so if you want to compare one sequence S against
  212.         many sequences, use .set_seq2(S) once and call .set_seq1(x)
  213.         repeatedly for each of the other sequences.
  214.  
  215.         See also set_seqs() and set_seq2().
  216.         '''
  217.         if a is self.a:
  218.             return None
  219.         
  220.         self.a = a
  221.         self.matching_blocks = None
  222.         self.opcodes = None
  223.  
  224.     
  225.     def set_seq2(self, b):
  226.         '''Set the second sequence to be compared.
  227.  
  228.         The first sequence to be compared is not changed.
  229.  
  230.         >>> s = SequenceMatcher(None, "abcd", "bcde")
  231.         >>> s.ratio()
  232.         0.75
  233.         >>> s.set_seq2("abcd")
  234.         >>> s.ratio()
  235.         1.0
  236.         >>>
  237.  
  238.         SequenceMatcher computes and caches detailed information about the
  239.         second sequence, so if you want to compare one sequence S against
  240.         many sequences, use .set_seq2(S) once and call .set_seq1(x)
  241.         repeatedly for each of the other sequences.
  242.  
  243.         See also set_seqs() and set_seq1().
  244.         '''
  245.         if b is self.b:
  246.             return None
  247.         
  248.         self.b = b
  249.         self.matching_blocks = None
  250.         self.opcodes = None
  251.         self.fullbcount = None
  252.         self._SequenceMatcher__chain_b()
  253.  
  254.     
  255.     def __chain_b(self):
  256.         b = self.b
  257.         n = len(b)
  258.         self.b2j = b2j = { }
  259.         populardict = { }
  260.         for i, elt in enumerate(b):
  261.             if elt in b2j:
  262.                 indices = b2j[elt]
  263.                 if n >= 200 and len(indices) * 100 > n:
  264.                     populardict[elt] = 1
  265.                     del indices[:]
  266.                 else:
  267.                     indices.append(i)
  268.             len(indices) * 100 > n
  269.             b2j[elt] = [
  270.                 i]
  271.         
  272.         for elt in populardict:
  273.             del b2j[elt]
  274.         
  275.         isjunk = self.isjunk
  276.         junkdict = { }
  277.         if isjunk:
  278.             for d in (populardict, b2j):
  279.                 for elt in d.keys():
  280.                     if isjunk(elt):
  281.                         junkdict[elt] = 1
  282.                         del d[elt]
  283.                         continue
  284.                 
  285.             
  286.         
  287.         self.isbjunk = junkdict.has_key
  288.         self.isbpopular = populardict.has_key
  289.  
  290.     
  291.     def find_longest_match(self, alo, ahi, blo, bhi):
  292.         '''Find longest matching block in a[alo:ahi] and b[blo:bhi].
  293.  
  294.         If isjunk is not defined:
  295.  
  296.         Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
  297.             alo <= i <= i+k <= ahi
  298.             blo <= j <= j+k <= bhi
  299.         and for all (i\',j\',k\') meeting those conditions,
  300.             k >= k\'
  301.             i <= i\'
  302.             and if i == i\', j <= j\'
  303.  
  304.         In other words, of all maximal matching blocks, return one that
  305.         starts earliest in a, and of all those maximal matching blocks that
  306.         start earliest in a, return the one that starts earliest in b.
  307.  
  308.         >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
  309.         >>> s.find_longest_match(0, 5, 0, 9)
  310.         (0, 4, 5)
  311.  
  312.         If isjunk is defined, first the longest matching block is
  313.         determined as above, but with the additional restriction that no
  314.         junk element appears in the block.  Then that block is extended as
  315.         far as possible by matching (only) junk elements on both sides.  So
  316.         the resulting block never matches on junk except as identical junk
  317.         happens to be adjacent to an "interesting" match.
  318.  
  319.         Here\'s the same example as before, but considering blanks to be
  320.         junk.  That prevents " abcd" from matching the " abcd" at the tail
  321.         end of the second sequence directly.  Instead only the "abcd" can
  322.         match, and matches the leftmost "abcd" in the second sequence:
  323.  
  324.         >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
  325.         >>> s.find_longest_match(0, 5, 0, 9)
  326.         (1, 0, 4)
  327.  
  328.         If no blocks match, return (alo, blo, 0).
  329.  
  330.         >>> s = SequenceMatcher(None, "ab", "c")
  331.         >>> s.find_longest_match(0, 2, 0, 1)
  332.         (0, 0, 0)
  333.         '''
  334.         (a, b, b2j, isbjunk) = (self.a, self.b, self.b2j, self.isbjunk)
  335.         besti = alo
  336.         bestj = blo
  337.         bestsize = 0
  338.         j2len = { }
  339.         nothing = []
  340.         for i in xrange(alo, ahi):
  341.             j2lenget = j2len.get
  342.             newj2len = { }
  343.             for j in b2j.get(a[i], nothing):
  344.                 if j < blo:
  345.                     continue
  346.                 
  347.                 if j >= bhi:
  348.                     break
  349.                 
  350.                 k = newj2len[j] = j2lenget(j - 1, 0) + 1
  351.                 if k > bestsize:
  352.                     besti = (i - k) + 1
  353.                     bestj = (j - k) + 1
  354.                     bestsize = k
  355.                     continue
  356.             
  357.             j2len = newj2len
  358.         
  359.         while besti > alo and bestj > blo and not isbjunk(b[bestj - 1]) and a[besti - 1] == b[bestj - 1]:
  360.             besti = besti - 1
  361.             bestj = bestj - 1
  362.             bestsize = bestsize + 1
  363.         while besti + bestsize < ahi and bestj + bestsize < bhi and not isbjunk(b[bestj + bestsize]) and a[besti + bestsize] == b[bestj + bestsize]:
  364.             bestsize += 1
  365.         while besti > alo and bestj > blo and isbjunk(b[bestj - 1]) and a[besti - 1] == b[bestj - 1]:
  366.             besti = besti - 1
  367.             bestj = bestj - 1
  368.             bestsize = bestsize + 1
  369.         while besti + bestsize < ahi and bestj + bestsize < bhi and isbjunk(b[bestj + bestsize]) and a[besti + bestsize] == b[bestj + bestsize]:
  370.             bestsize = bestsize + 1
  371.         return (besti, bestj, bestsize)
  372.  
  373.     
  374.     def get_matching_blocks(self):
  375.         '''Return list of triples describing matching subsequences.
  376.  
  377.         Each triple is of the form (i, j, n), and means that
  378.         a[i:i+n] == b[j:j+n].  The triples are monotonically increasing in
  379.         i and in j.
  380.  
  381.         The last triple is a dummy, (len(a), len(b), 0), and is the only
  382.         triple with n==0.
  383.  
  384.         >>> s = SequenceMatcher(None, "abxcd", "abcd")
  385.         >>> s.get_matching_blocks()
  386.         [(0, 0, 2), (3, 2, 2), (5, 4, 0)]
  387.         '''
  388.         if self.matching_blocks is not None:
  389.             return self.matching_blocks
  390.         
  391.         self.matching_blocks = []
  392.         la = len(self.a)
  393.         lb = len(self.b)
  394.         self._SequenceMatcher__helper(0, la, 0, lb, self.matching_blocks)
  395.         self.matching_blocks.append((la, lb, 0))
  396.         return self.matching_blocks
  397.  
  398.     
  399.     def __helper(self, alo, ahi, blo, bhi, answer):
  400.         (i, j, k) = x = self.find_longest_match(alo, ahi, blo, bhi)
  401.         if k:
  402.             if alo < i and blo < j:
  403.                 self._SequenceMatcher__helper(alo, i, blo, j, answer)
  404.             
  405.             answer.append(x)
  406.             if i + k < ahi and j + k < bhi:
  407.                 self._SequenceMatcher__helper(i + k, ahi, j + k, bhi, answer)
  408.             
  409.         
  410.  
  411.     
  412.     def get_opcodes(self):
  413.         '''Return list of 5-tuples describing how to turn a into b.
  414.  
  415.         Each tuple is of the form (tag, i1, i2, j1, j2).  The first tuple
  416.         has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the
  417.         tuple preceding it, and likewise for j1 == the previous j2.
  418.  
  419.         The tags are strings, with these meanings:
  420.  
  421.         \'replace\':  a[i1:i2] should be replaced by b[j1:j2]
  422.         \'delete\':   a[i1:i2] should be deleted.
  423.                     Note that j1==j2 in this case.
  424.         \'insert\':   b[j1:j2] should be inserted at a[i1:i1].
  425.                     Note that i1==i2 in this case.
  426.         \'equal\':    a[i1:i2] == b[j1:j2]
  427.  
  428.         >>> a = "qabxcd"
  429.         >>> b = "abycdf"
  430.         >>> s = SequenceMatcher(None, a, b)
  431.         >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
  432.         ...    print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
  433.         ...           (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
  434.          delete a[0:1] (q) b[0:0] ()
  435.           equal a[1:3] (ab) b[0:2] (ab)
  436.         replace a[3:4] (x) b[2:3] (y)
  437.           equal a[4:6] (cd) b[3:5] (cd)
  438.          insert a[6:6] () b[5:6] (f)
  439.         '''
  440.         if self.opcodes is not None:
  441.             return self.opcodes
  442.         
  443.         i = j = 0
  444.         self.opcodes = answer = []
  445.         for ai, bj, size in self.get_matching_blocks():
  446.             tag = ''
  447.             if i < ai and j < bj:
  448.                 tag = 'replace'
  449.             elif i < ai:
  450.                 tag = 'delete'
  451.             elif j < bj:
  452.                 tag = 'insert'
  453.             
  454.             if tag:
  455.                 answer.append((tag, i, ai, j, bj))
  456.             
  457.             i = ai + size
  458.             j = bj + size
  459.             if size:
  460.                 answer.append(('equal', ai, i, bj, j))
  461.                 continue
  462.         
  463.         return answer
  464.  
  465.     
  466.     def get_grouped_opcodes(self, n = 3):
  467.         """ Isolate change clusters by eliminating ranges with no changes.
  468.  
  469.         Return a generator of groups with upto n lines of context.
  470.         Each group is in the same format as returned by get_opcodes().
  471.  
  472.         >>> from pprint import pprint
  473.         >>> a = map(str, range(1,40))
  474.         >>> b = a[:]
  475.         >>> b[8:8] = ['i']     # Make an insertion
  476.         >>> b[20] += 'x'       # Make a replacement
  477.         >>> b[23:28] = []      # Make a deletion
  478.         >>> b[30] += 'y'       # Make another replacement
  479.         >>> pprint(list(SequenceMatcher(None,a,b).get_grouped_opcodes()))
  480.         [[('equal', 5, 8, 5, 8), ('insert', 8, 8, 8, 9), ('equal', 8, 11, 9, 12)],
  481.          [('equal', 16, 19, 17, 20),
  482.           ('replace', 19, 20, 20, 21),
  483.           ('equal', 20, 22, 21, 23),
  484.           ('delete', 22, 27, 23, 23),
  485.           ('equal', 27, 30, 23, 26)],
  486.          [('equal', 31, 34, 27, 30),
  487.           ('replace', 34, 35, 30, 31),
  488.           ('equal', 35, 38, 31, 34)]]
  489.         """
  490.         codes = self.get_opcodes()
  491.         if not codes:
  492.             codes = [
  493.                 ('equal', 0, 1, 0, 1)]
  494.         
  495.         if codes[0][0] == 'equal':
  496.             (tag, i1, i2, j1, j2) = codes[0]
  497.             codes[0] = (tag, max(i1, i2 - n), i2, max(j1, j2 - n), j2)
  498.         
  499.         if codes[-1][0] == 'equal':
  500.             (tag, i1, i2, j1, j2) = codes[-1]
  501.             codes[-1] = (tag, i1, min(i2, i1 + n), j1, min(j2, j1 + n))
  502.         
  503.         nn = n + n
  504.         group = []
  505.         for tag, i1, i2, j1, j2 in codes:
  506.             if tag == 'equal' and i2 - i1 > nn:
  507.                 group.append((tag, i1, min(i2, i1 + n), j1, min(j2, j1 + n)))
  508.                 yield group
  509.                 group = []
  510.                 i1 = max(i1, i2 - n)
  511.                 j1 = max(j1, j2 - n)
  512.             
  513.             group.append((tag, i1, i2, j1, j2))
  514.         
  515.         if group:
  516.             if len(group) == 1:
  517.                 pass
  518.             if not (group[0][0] == 'equal'):
  519.                 yield group
  520.             
  521.  
  522.     
  523.     def ratio(self):
  524.         '''Return a measure of the sequences\' similarity (float in [0,1]).
  525.  
  526.         Where T is the total number of elements in both sequences, and
  527.         M is the number of matches, this is 2.0*M / T.
  528.         Note that this is 1 if the sequences are identical, and 0 if
  529.         they have nothing in common.
  530.  
  531.         .ratio() is expensive to compute if you haven\'t already computed
  532.         .get_matching_blocks() or .get_opcodes(), in which case you may
  533.         want to try .quick_ratio() or .real_quick_ratio() first to get an
  534.         upper bound.
  535.  
  536.         >>> s = SequenceMatcher(None, "abcd", "bcde")
  537.         >>> s.ratio()
  538.         0.75
  539.         >>> s.quick_ratio()
  540.         0.75
  541.         >>> s.real_quick_ratio()
  542.         1.0
  543.         '''
  544.         matches = reduce((lambda sum, triple: sum + triple[-1]), self.get_matching_blocks(), 0)
  545.         return _calculate_ratio(matches, len(self.a) + len(self.b))
  546.  
  547.     
  548.     def quick_ratio(self):
  549.         """Return an upper bound on ratio() relatively quickly.
  550.  
  551.         This isn't defined beyond that it is an upper bound on .ratio(), and
  552.         is faster to compute.
  553.         """
  554.         if self.fullbcount is None:
  555.             self.fullbcount = fullbcount = { }
  556.             for elt in self.b:
  557.                 fullbcount[elt] = fullbcount.get(elt, 0) + 1
  558.             
  559.         
  560.         fullbcount = self.fullbcount
  561.         avail = { }
  562.         availhas = avail.has_key
  563.         matches = 0
  564.         for elt in self.a:
  565.             if availhas(elt):
  566.                 numb = avail[elt]
  567.             else:
  568.                 numb = fullbcount.get(elt, 0)
  569.             avail[elt] = numb - 1
  570.             if numb > 0:
  571.                 matches = matches + 1
  572.                 continue
  573.         
  574.         return _calculate_ratio(matches, len(self.a) + len(self.b))
  575.  
  576.     
  577.     def real_quick_ratio(self):
  578.         """Return an upper bound on ratio() very quickly.
  579.  
  580.         This isn't defined beyond that it is an upper bound on .ratio(), and
  581.         is faster to compute than either .ratio() or .quick_ratio().
  582.         """
  583.         la = len(self.a)
  584.         lb = len(self.b)
  585.         return _calculate_ratio(min(la, lb), la + lb)
  586.  
  587.  
  588.  
  589. def get_close_matches(word, possibilities, n = 3, cutoff = 0.59999999999999998):
  590.     '''Use SequenceMatcher to return list of the best "good enough" matches.
  591.  
  592.     word is a sequence for which close matches are desired (typically a
  593.     string).
  594.  
  595.     possibilities is a list of sequences against which to match word
  596.     (typically a list of strings).
  597.  
  598.     Optional arg n (default 3) is the maximum number of close matches to
  599.     return.  n must be > 0.
  600.  
  601.     Optional arg cutoff (default 0.6) is a float in [0, 1].  Possibilities
  602.     that don\'t score at least that similar to word are ignored.
  603.  
  604.     The best (no more than n) matches among the possibilities are returned
  605.     in a list, sorted by similarity score, most similar first.
  606.  
  607.     >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])
  608.     [\'apple\', \'ape\']
  609.     >>> import keyword as _keyword
  610.     >>> get_close_matches("wheel", _keyword.kwlist)
  611.     [\'while\']
  612.     >>> get_close_matches("apple", _keyword.kwlist)
  613.     []
  614.     >>> get_close_matches("accept", _keyword.kwlist)
  615.     [\'except\']
  616.     '''
  617.     if not n > 0:
  618.         raise ValueError('n must be > 0: %r' % (n,))
  619.     
  620.     if cutoff <= cutoff:
  621.         pass
  622.     elif not cutoff <= 1.0:
  623.         raise ValueError('cutoff must be in [0.0, 1.0]: %r' % (cutoff,))
  624.     
  625.     result = []
  626.     s = SequenceMatcher()
  627.     s.set_seq2(word)
  628.     for x in possibilities:
  629.         s.set_seq1(x)
  630.         if s.real_quick_ratio() >= cutoff and s.quick_ratio() >= cutoff and s.ratio() >= cutoff:
  631.             result.append((s.ratio(), x))
  632.             continue
  633.         0.0
  634.     
  635.     result = heapq.nlargest(n, result)
  636.     return [ x for score, x in result ]
  637.  
  638.  
  639. def _count_leading(line, ch):
  640.     """
  641.     Return number of `ch` characters at the start of `line`.
  642.  
  643.     Example:
  644.  
  645.     >>> _count_leading('   abc', ' ')
  646.     3
  647.     """
  648.     i = 0
  649.     n = len(line)
  650.     while i < n and line[i] == ch:
  651.         i += 1
  652.     return i
  653.  
  654.  
  655. class Differ:
  656.     """
  657.     Differ is a class for comparing sequences of lines of text, and
  658.     producing human-readable differences or deltas.  Differ uses
  659.     SequenceMatcher both to compare sequences of lines, and to compare
  660.     sequences of characters within similar (near-matching) lines.
  661.  
  662.     Each line of a Differ delta begins with a two-letter code:
  663.  
  664.         '- '    line unique to sequence 1
  665.         '+ '    line unique to sequence 2
  666.         '  '    line common to both sequences
  667.         '? '    line not present in either input sequence
  668.  
  669.     Lines beginning with '? ' attempt to guide the eye to intraline
  670.     differences, and were not present in either input sequence.  These lines
  671.     can be confusing if the sequences contain tab characters.
  672.  
  673.     Note that Differ makes no claim to produce a *minimal* diff.  To the
  674.     contrary, minimal diffs are often counter-intuitive, because they synch
  675.     up anywhere possible, sometimes accidental matches 100 pages apart.
  676.     Restricting synch points to contiguous matches preserves some notion of
  677.     locality, at the occasional cost of producing a longer diff.
  678.  
  679.     Example: Comparing two texts.
  680.  
  681.     First we set up the texts, sequences of individual single-line strings
  682.     ending with newlines (such sequences can also be obtained from the
  683.     `readlines()` method of file-like objects):
  684.  
  685.     >>> text1 = '''  1. Beautiful is better than ugly.
  686.     ...   2. Explicit is better than implicit.
  687.     ...   3. Simple is better than complex.
  688.     ...   4. Complex is better than complicated.
  689.     ... '''.splitlines(1)
  690.     >>> len(text1)
  691.     4
  692.     >>> text1[0][-1]
  693.     '\\n'
  694.     >>> text2 = '''  1. Beautiful is better than ugly.
  695.     ...   3.   Simple is better than complex.
  696.     ...   4. Complicated is better than complex.
  697.     ...   5. Flat is better than nested.
  698.     ... '''.splitlines(1)
  699.  
  700.     Next we instantiate a Differ object:
  701.  
  702.     >>> d = Differ()
  703.  
  704.     Note that when instantiating a Differ object we may pass functions to
  705.     filter out line and character 'junk'.  See Differ.__init__ for details.
  706.  
  707.     Finally, we compare the two:
  708.  
  709.     >>> result = list(d.compare(text1, text2))
  710.  
  711.     'result' is a list of strings, so let's pretty-print it:
  712.  
  713.     >>> from pprint import pprint as _pprint
  714.     >>> _pprint(result)
  715.     ['    1. Beautiful is better than ugly.\\n',
  716.      '-   2. Explicit is better than implicit.\\n',
  717.      '-   3. Simple is better than complex.\\n',
  718.      '+   3.   Simple is better than complex.\\n',
  719.      '?     ++\\n',
  720.      '-   4. Complex is better than complicated.\\n',
  721.      '?            ^                     ---- ^\\n',
  722.      '+   4. Complicated is better than complex.\\n',
  723.      '?           ++++ ^                      ^\\n',
  724.      '+   5. Flat is better than nested.\\n']
  725.  
  726.     As a single multi-line string it looks like this:
  727.  
  728.     >>> print ''.join(result),
  729.         1. Beautiful is better than ugly.
  730.     -   2. Explicit is better than implicit.
  731.     -   3. Simple is better than complex.
  732.     +   3.   Simple is better than complex.
  733.     ?     ++
  734.     -   4. Complex is better than complicated.
  735.     ?            ^                     ---- ^
  736.     +   4. Complicated is better than complex.
  737.     ?           ++++ ^                      ^
  738.     +   5. Flat is better than nested.
  739.  
  740.     Methods:
  741.  
  742.     __init__(linejunk=None, charjunk=None)
  743.         Construct a text differencer, with optional filters.
  744.  
  745.     compare(a, b)
  746.         Compare two sequences of lines; generate the resulting delta.
  747.     """
  748.     
  749.     def __init__(self, linejunk = None, charjunk = None):
  750.         '''
  751.         Construct a text differencer, with optional filters.
  752.  
  753.         The two optional keyword parameters are for filter functions:
  754.  
  755.         - `linejunk`: A function that should accept a single string argument,
  756.           and return true iff the string is junk. The module-level function
  757.           `IS_LINE_JUNK` may be used to filter out lines without visible
  758.           characters, except for at most one splat (\'#\').  It is recommended
  759.           to leave linejunk None; as of Python 2.3, the underlying
  760.           SequenceMatcher class has grown an adaptive notion of "noise" lines
  761.           that\'s better than any static definition the author has ever been
  762.           able to craft.
  763.  
  764.         - `charjunk`: A function that should accept a string of length 1. The
  765.           module-level function `IS_CHARACTER_JUNK` may be used to filter out
  766.           whitespace characters (a blank or tab; **note**: bad idea to include
  767.           newline in this!).  Use of IS_CHARACTER_JUNK is recommended.
  768.         '''
  769.         self.linejunk = linejunk
  770.         self.charjunk = charjunk
  771.  
  772.     
  773.     def compare(self, a, b):
  774.         """
  775.         Compare two sequences of lines; generate the resulting delta.
  776.  
  777.         Each sequence must contain individual single-line strings ending with
  778.         newlines. Such sequences can be obtained from the `readlines()` method
  779.         of file-like objects.  The delta generated also consists of newline-
  780.         terminated strings, ready to be printed as-is via the writeline()
  781.         method of a file-like object.
  782.  
  783.         Example:
  784.  
  785.         >>> print ''.join(Differ().compare('one\\ntwo\\nthree\\n'.splitlines(1),
  786.         ...                                'ore\\ntree\\nemu\\n'.splitlines(1))),
  787.         - one
  788.         ?  ^
  789.         + ore
  790.         ?  ^
  791.         - two
  792.         - three
  793.         ?  -
  794.         + tree
  795.         + emu
  796.         """
  797.         cruncher = SequenceMatcher(self.linejunk, a, b)
  798.         for tag, alo, ahi, blo, bhi in cruncher.get_opcodes():
  799.             if tag == 'replace':
  800.                 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
  801.             elif tag == 'delete':
  802.                 g = self._dump('-', a, alo, ahi)
  803.             elif tag == 'insert':
  804.                 g = self._dump('+', b, blo, bhi)
  805.             elif tag == 'equal':
  806.                 g = self._dump(' ', a, alo, ahi)
  807.             else:
  808.                 raise ValueError, 'unknown tag %r' % (tag,)
  809.             for line in g:
  810.                 yield line
  811.             
  812.         
  813.  
  814.     
  815.     def _dump(self, tag, x, lo, hi):
  816.         '''Generate comparison results for a same-tagged range.'''
  817.         for i in xrange(lo, hi):
  818.             yield '%s %s' % (tag, x[i])
  819.         
  820.  
  821.     
  822.     def _plain_replace(self, a, alo, ahi, b, blo, bhi):
  823.         if not alo < ahi or blo < bhi:
  824.             raise AssertionError
  825.         if bhi - blo < ahi - alo:
  826.             first = self._dump('+', b, blo, bhi)
  827.             second = self._dump('-', a, alo, ahi)
  828.         else:
  829.             first = self._dump('-', a, alo, ahi)
  830.             second = self._dump('+', b, blo, bhi)
  831.         for g in (first, second):
  832.             for line in g:
  833.                 yield line
  834.             
  835.         
  836.  
  837.     
  838.     def _fancy_replace(self, a, alo, ahi, b, blo, bhi):
  839.         """
  840.         When replacing one block of lines with another, search the blocks
  841.         for *similar* lines; the best-matching pair (if any) is used as a
  842.         synch point, and intraline difference marking is done on the
  843.         similar pair. Lots of work, but often worth it.
  844.  
  845.         Example:
  846.  
  847.         >>> d = Differ()
  848.         >>> results = d._fancy_replace(['abcDefghiJkl\\n'], 0, 1,
  849.         ...                            ['abcdefGhijkl\\n'], 0, 1)
  850.         >>> print ''.join(results),
  851.         - abcDefghiJkl
  852.         ?    ^  ^  ^
  853.         + abcdefGhijkl
  854.         ?    ^  ^  ^
  855.         """
  856.         (best_ratio, cutoff) = (0.73999999999999999, 0.75)
  857.         cruncher = SequenceMatcher(self.charjunk)
  858.         (eqi, eqj) = (None, None)
  859.         for j in xrange(blo, bhi):
  860.             bj = b[j]
  861.             cruncher.set_seq2(bj)
  862.             for i in xrange(alo, ahi):
  863.                 ai = a[i]
  864.                 if ai == bj:
  865.                     if eqi is None:
  866.                         eqi = i
  867.                         eqj = j
  868.                         continue
  869.                     continue
  870.                 
  871.                 cruncher.set_seq1(ai)
  872.                 if cruncher.real_quick_ratio() > best_ratio and cruncher.quick_ratio() > best_ratio and cruncher.ratio() > best_ratio:
  873.                     best_ratio = cruncher.ratio()
  874.                     best_i = i
  875.                     best_j = j
  876.                     continue
  877.             
  878.         
  879.         if best_ratio < cutoff:
  880.             if eqi is None:
  881.                 for line in self._plain_replace(a, alo, ahi, b, blo, bhi):
  882.                     yield line
  883.                 
  884.                 return None
  885.             
  886.             best_i = eqi
  887.             best_j = eqj
  888.             best_ratio = 1.0
  889.         else:
  890.             eqi = None
  891.         for line in self._fancy_helper(a, alo, best_i, b, blo, best_j):
  892.             yield line
  893.         
  894.         aelt = a[best_i]
  895.         belt = b[best_j]
  896.         if eqi is None:
  897.             atags = btags = ''
  898.             cruncher.set_seqs(aelt, belt)
  899.             for tag, ai1, ai2, bj1, bj2 in cruncher.get_opcodes():
  900.                 la = ai2 - ai1
  901.                 lb = bj2 - bj1
  902.                 if tag == 'replace':
  903.                     atags += '^' * la
  904.                     btags += '^' * lb
  905.                     continue
  906.                 if tag == 'delete':
  907.                     atags += '-' * la
  908.                     continue
  909.                 if tag == 'insert':
  910.                     btags += '+' * lb
  911.                     continue
  912.                 if tag == 'equal':
  913.                     atags += ' ' * la
  914.                     btags += ' ' * lb
  915.                     continue
  916.                 raise ValueError, 'unknown tag %r' % (tag,)
  917.             
  918.             for line in self._qformat(aelt, belt, atags, btags):
  919.                 yield line
  920.             
  921.         else:
  922.             yield '  ' + aelt
  923.         for line in self._fancy_helper(a, best_i + 1, ahi, b, best_j + 1, bhi):
  924.             yield line
  925.         
  926.  
  927.     
  928.     def _fancy_helper(self, a, alo, ahi, b, blo, bhi):
  929.         g = []
  930.         if alo < ahi:
  931.             if blo < bhi:
  932.                 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
  933.             else:
  934.                 g = self._dump('-', a, alo, ahi)
  935.         elif blo < bhi:
  936.             g = self._dump('+', b, blo, bhi)
  937.         
  938.         for line in g:
  939.             yield line
  940.         
  941.  
  942.     
  943.     def _qformat(self, aline, bline, atags, btags):
  944.         '''
  945.         Format "?" output and deal with leading tabs.
  946.  
  947.         Example:
  948.  
  949.         >>> d = Differ()
  950.         >>> results = d._qformat(\'\\tabcDefghiJkl\\n\', \'\\t\\tabcdefGhijkl\\n\',
  951.         ...                      \'  ^ ^  ^      \', \'+  ^ ^  ^      \')
  952.         >>> for line in results: print repr(line)
  953.         ...
  954.         \'- \\tabcDefghiJkl\\n\'
  955.         \'? \\t ^ ^  ^\\n\'
  956.         \'+ \\t\\tabcdefGhijkl\\n\'
  957.         \'? \\t  ^ ^  ^\\n\'
  958.         '''
  959.         common = min(_count_leading(aline, '\t'), _count_leading(bline, '\t'))
  960.         common = min(common, _count_leading(atags[:common], ' '))
  961.         atags = atags[common:].rstrip()
  962.         btags = btags[common:].rstrip()
  963.         yield '- ' + aline
  964.         if atags:
  965.             yield '? %s%s\n' % ('\t' * common, atags)
  966.         
  967.         yield '+ ' + bline
  968.         if btags:
  969.             yield '? %s%s\n' % ('\t' * common, btags)
  970.         
  971.  
  972.  
  973. import re
  974.  
  975. def IS_LINE_JUNK(line, pat = re.compile('\\s*#?\\s*$').match):
  976.     """
  977.     Return 1 for ignorable line: iff `line` is blank or contains a single '#'.
  978.  
  979.     Examples:
  980.  
  981.     >>> IS_LINE_JUNK('\\n')
  982.     True
  983.     >>> IS_LINE_JUNK('  #   \\n')
  984.     True
  985.     >>> IS_LINE_JUNK('hello\\n')
  986.     False
  987.     """
  988.     return pat(line) is not None
  989.  
  990.  
  991. def IS_CHARACTER_JUNK(ch, ws = ' \t'):
  992.     """
  993.     Return 1 for ignorable character: iff `ch` is a space or tab.
  994.  
  995.     Examples:
  996.  
  997.     >>> IS_CHARACTER_JUNK(' ')
  998.     True
  999.     >>> IS_CHARACTER_JUNK('\\t')
  1000.     True
  1001.     >>> IS_CHARACTER_JUNK('\\n')
  1002.     False
  1003.     >>> IS_CHARACTER_JUNK('x')
  1004.     False
  1005.     """
  1006.     return ch in ws
  1007.  
  1008.  
  1009. def unified_diff(a, b, fromfile = '', tofile = '', fromfiledate = '', tofiledate = '', n = 3, lineterm = '\n'):
  1010.     '''
  1011.     Compare two sequences of lines; generate the delta as a unified diff.
  1012.  
  1013.     Unified diffs are a compact way of showing line changes and a few
  1014.     lines of context.  The number of context lines is set by \'n\' which
  1015.     defaults to three.
  1016.  
  1017.     By default, the diff control lines (those with ---, +++, or @@) are
  1018.     created with a trailing newline.  This is helpful so that inputs
  1019.     created from file.readlines() result in diffs that are suitable for
  1020.     file.writelines() since both the inputs and outputs have trailing
  1021.     newlines.
  1022.  
  1023.     For inputs that do not have trailing newlines, set the lineterm
  1024.     argument to "" so that the output will be uniformly newline free.
  1025.  
  1026.     The unidiff format normally has a header for filenames and modification
  1027.     times.  Any or all of these may be specified using strings for
  1028.     \'fromfile\', \'tofile\', \'fromfiledate\', and \'tofiledate\'.  The modification
  1029.     times are normally expressed in the format returned by time.ctime().
  1030.  
  1031.     Example:
  1032.  
  1033.     >>> for line in unified_diff(\'one two three four\'.split(),
  1034.     ...             \'zero one tree four\'.split(), \'Original\', \'Current\',
  1035.     ...             \'Sat Jan 26 23:30:50 1991\', \'Fri Jun 06 10:20:52 2003\',
  1036.     ...             lineterm=\'\'):
  1037.     ...     print line
  1038.     --- Original Sat Jan 26 23:30:50 1991
  1039.     +++ Current Fri Jun 06 10:20:52 2003
  1040.     @@ -1,4 +1,4 @@
  1041.     +zero
  1042.      one
  1043.     -two
  1044.     -three
  1045.     +tree
  1046.      four
  1047.     '''
  1048.     started = False
  1049.     for group in SequenceMatcher(None, a, b).get_grouped_opcodes(n):
  1050.         if not started:
  1051.             yield '--- %s %s%s' % (fromfile, fromfiledate, lineterm)
  1052.             yield '+++ %s %s%s' % (tofile, tofiledate, lineterm)
  1053.             started = True
  1054.         
  1055.         (i1, i2, j1, j2) = (group[0][1], group[-1][2], group[0][3], group[-1][4])
  1056.         yield '@@ -%d,%d +%d,%d @@%s' % (i1 + 1, i2 - i1, j1 + 1, j2 - j1, lineterm)
  1057.         for tag, i1, i2, j1, j2 in group:
  1058.             if tag == 'equal':
  1059.                 for line in a[i1:i2]:
  1060.                     yield ' ' + line
  1061.                 
  1062.                 continue
  1063.             
  1064.             if tag == 'replace' or tag == 'delete':
  1065.                 for line in a[i1:i2]:
  1066.                     yield '-' + line
  1067.                 
  1068.             
  1069.             if tag == 'replace' or tag == 'insert':
  1070.                 for line in b[j1:j2]:
  1071.                     yield '+' + line
  1072.                 
  1073.         
  1074.     
  1075.  
  1076.  
  1077. def context_diff(a, b, fromfile = '', tofile = '', fromfiledate = '', tofiledate = '', n = 3, lineterm = '\n'):
  1078.     '''
  1079.     Compare two sequences of lines; generate the delta as a context diff.
  1080.  
  1081.     Context diffs are a compact way of showing line changes and a few
  1082.     lines of context.  The number of context lines is set by \'n\' which
  1083.     defaults to three.
  1084.  
  1085.     By default, the diff control lines (those with *** or ---) are
  1086.     created with a trailing newline.  This is helpful so that inputs
  1087.     created from file.readlines() result in diffs that are suitable for
  1088.     file.writelines() since both the inputs and outputs have trailing
  1089.     newlines.
  1090.  
  1091.     For inputs that do not have trailing newlines, set the lineterm
  1092.     argument to "" so that the output will be uniformly newline free.
  1093.  
  1094.     The context diff format normally has a header for filenames and
  1095.     modification times.  Any or all of these may be specified using
  1096.     strings for \'fromfile\', \'tofile\', \'fromfiledate\', and \'tofiledate\'.
  1097.     The modification times are normally expressed in the format returned
  1098.     by time.ctime().  If not specified, the strings default to blanks.
  1099.  
  1100.     Example:
  1101.  
  1102.     >>> print \'\'.join(context_diff(\'one\\ntwo\\nthree\\nfour\\n\'.splitlines(1),
  1103.     ...       \'zero\\none\\ntree\\nfour\\n\'.splitlines(1), \'Original\', \'Current\',
  1104.     ...       \'Sat Jan 26 23:30:50 1991\', \'Fri Jun 06 10:22:46 2003\')),
  1105.     *** Original Sat Jan 26 23:30:50 1991
  1106.     --- Current Fri Jun 06 10:22:46 2003
  1107.     ***************
  1108.     *** 1,4 ****
  1109.       one
  1110.     ! two
  1111.     ! three
  1112.       four
  1113.     --- 1,4 ----
  1114.     + zero
  1115.       one
  1116.     ! tree
  1117.       four
  1118.     '''
  1119.     started = False
  1120.     prefixmap = {
  1121.         'insert': '+ ',
  1122.         'delete': '- ',
  1123.         'replace': '! ',
  1124.         'equal': '  ' }
  1125.     for group in SequenceMatcher(None, a, b).get_grouped_opcodes(n):
  1126.         if not started:
  1127.             yield '*** %s %s%s' % (fromfile, fromfiledate, lineterm)
  1128.             yield '--- %s %s%s' % (tofile, tofiledate, lineterm)
  1129.             started = True
  1130.         
  1131.         yield '***************%s' % (lineterm,)
  1132.         if group[-1][2] - group[0][1] >= 2:
  1133.             yield '*** %d,%d ****%s' % (group[0][1] + 1, group[-1][2], lineterm)
  1134.         else:
  1135.             yield '*** %d ****%s' % (group[-1][2], lineterm)
  1136.         visiblechanges = _[1]
  1137.         if visiblechanges:
  1138.             for tag, i1, i2, _, _ in group:
  1139.                 if tag != 'insert':
  1140.                     for line in a[i1:i2]:
  1141.                         yield prefixmap[tag] + line
  1142.                     
  1143.                 []
  1144.             
  1145.         
  1146.         if group[-1][4] - group[0][3] >= 2:
  1147.             yield '--- %d,%d ----%s' % (group[0][3] + 1, group[-1][4], lineterm)
  1148.         else:
  1149.             yield '--- %d ----%s' % (group[-1][4], lineterm)
  1150.         visiblechanges = _[1]
  1151.         if visiblechanges:
  1152.             for tag, _, _, j1, j2 in group:
  1153.                 if tag != 'delete':
  1154.                     for line in b[j1:j2]:
  1155.                         yield prefixmap[tag] + line
  1156.                     
  1157.                 []
  1158.             
  1159.         []
  1160.     
  1161.  
  1162.  
  1163. def ndiff(a, b, linejunk = None, charjunk = IS_CHARACTER_JUNK):
  1164.     '''
  1165.     Compare `a` and `b` (lists of strings); return a `Differ`-style delta.
  1166.  
  1167.     Optional keyword parameters `linejunk` and `charjunk` are for filter
  1168.     functions (or None):
  1169.  
  1170.     - linejunk: A function that should accept a single string argument, and
  1171.       return true iff the string is junk.  The default is None, and is
  1172.       recommended; as of Python 2.3, an adaptive notion of "noise" lines is
  1173.       used that does a good job on its own.
  1174.  
  1175.     - charjunk: A function that should accept a string of length 1. The
  1176.       default is module-level function IS_CHARACTER_JUNK, which filters out
  1177.       whitespace characters (a blank or tab; note: bad idea to include newline
  1178.       in this!).
  1179.  
  1180.     Tools/scripts/ndiff.py is a command-line front-end to this function.
  1181.  
  1182.     Example:
  1183.  
  1184.     >>> diff = ndiff(\'one\\ntwo\\nthree\\n\'.splitlines(1),
  1185.     ...              \'ore\\ntree\\nemu\\n\'.splitlines(1))
  1186.     >>> print \'\'.join(diff),
  1187.     - one
  1188.     ?  ^
  1189.     + ore
  1190.     ?  ^
  1191.     - two
  1192.     - three
  1193.     ?  -
  1194.     + tree
  1195.     + emu
  1196.     '''
  1197.     return Differ(linejunk, charjunk).compare(a, b)
  1198.  
  1199.  
  1200. def _mdiff(fromlines, tolines, context = None, linejunk = None, charjunk = IS_CHARACTER_JUNK):
  1201.     '''Returns generator yielding marked up from/to side by side differences.
  1202.  
  1203.     Arguments:
  1204.     fromlines -- list of text lines to compared to tolines
  1205.     tolines -- list of text lines to be compared to fromlines
  1206.     context -- number of context lines to display on each side of difference,
  1207.                if None, all from/to text lines will be generated.
  1208.     linejunk -- passed on to ndiff (see ndiff documentation)
  1209.     charjunk -- passed on to ndiff (see ndiff documentation)
  1210.  
  1211.     This function returns an interator which returns a tuple:
  1212.     (from line tuple, to line tuple, boolean flag)
  1213.  
  1214.     from/to line tuple -- (line num, line text)
  1215.         line num -- integer or None (to indicate a context seperation)
  1216.         line text -- original line text with following markers inserted:
  1217.             \'\x00+\' -- marks start of added text
  1218.             \'\x00-\' -- marks start of deleted text
  1219.             \'\x00^\' -- marks start of changed text
  1220.             \'\x01\' -- marks end of added/deleted/changed text
  1221.  
  1222.     boolean flag -- None indicates context separation, True indicates
  1223.         either "from" or "to" line contains a change, otherwise False.
  1224.  
  1225.     This function/iterator was originally developed to generate side by side
  1226.     file difference for making HTML pages (see HtmlDiff class for example
  1227.     usage).
  1228.  
  1229.     Note, this function utilizes the ndiff function to generate the side by
  1230.     side difference markup.  Optional ndiff arguments may be passed to this
  1231.     function and they in turn will be passed to ndiff.
  1232.     '''
  1233.     import re as re
  1234.     change_re = re.compile('(\\++|\\-+|\\^+)')
  1235.     diff_lines_iterator = ndiff(fromlines, tolines, linejunk, charjunk)
  1236.     
  1237.     def _make_line(lines, format_key, side, num_lines = [
  1238.         0,
  1239.         0]):
  1240.         '''Returns line of text with user\'s change markup and line formatting.
  1241.  
  1242.         lines -- list of lines from the ndiff generator to produce a line of
  1243.                  text from.  When producing the line of text to return, the
  1244.                  lines used are removed from this list.
  1245.         format_key -- \'+\' return first line in list with "add" markup around
  1246.                           the entire line.
  1247.                       \'-\' return first line in list with "delete" markup around
  1248.                           the entire line.
  1249.                       \'?\' return first line in list with add/delete/change
  1250.                           intraline markup (indices obtained from second line)
  1251.                       None return first line in list with no markup
  1252.         side -- indice into the num_lines list (0=from,1=to)
  1253.         num_lines -- from/to current line number.  This is NOT intended to be a
  1254.                      passed parameter.  It is present as a keyword argument to
  1255.                      maintain memory of the current line numbers between calls
  1256.                      of this function.
  1257.  
  1258.         Note, this function is purposefully not defined at the module scope so
  1259.         that data it needs from its parent function (within whose context it
  1260.         is defined) does not need to be of module scope.
  1261.         '''
  1262.         num_lines[side] += 1
  1263.         if format_key is None:
  1264.             return (num_lines[side], lines.pop(0)[2:])
  1265.         
  1266.         if format_key == '?':
  1267.             text = lines.pop(0)
  1268.             markers = lines.pop(0)
  1269.             sub_info = []
  1270.             
  1271.             def record_sub_info(match_object, sub_info = sub_info):
  1272.                 sub_info.append([
  1273.                     match_object.group(1)[0],
  1274.                     match_object.span()])
  1275.                 return match_object.group(1)
  1276.  
  1277.             change_re.sub(record_sub_info, markers)
  1278.             for begin, end in sub_info[::-1]:
  1279.                 text = text[0:begin] + '\x00' + key + text[begin:end] + '\x01' + text[end:]
  1280.             
  1281.             text = text[2:]
  1282.         else:
  1283.             text = lines.pop(0)[2:]
  1284.             if not text:
  1285.                 text = ' '
  1286.             
  1287.             text = '\x00' + format_key + text + '\x01'
  1288.         return (num_lines[side], text)
  1289.  
  1290.     
  1291.     def _line_iterator():
  1292.         '''Yields from/to lines of text with a change indication.
  1293.  
  1294.         This function is an iterator.  It itself pulls lines from a
  1295.         differencing iterator, processes them and yields them.  When it can
  1296.         it yields both a "from" and a "to" line, otherwise it will yield one
  1297.         or the other.  In addition to yielding the lines of from/to text, a
  1298.         boolean flag is yielded to indicate if the text line(s) have
  1299.         differences in them.
  1300.  
  1301.         Note, this function is purposefully not defined at the module scope so
  1302.         that data it needs from its parent function (within whose context it
  1303.         is defined) does not need to be of module scope.
  1304.         '''
  1305.         lines = []
  1306.         (num_blanks_pending, num_blanks_to_yield) = (0, 0)
  1307.         for line in lines:
  1308.             continue
  1309.             s = _[1](_[1][line[0]])
  1310.             if s.startswith('X'):
  1311.                 num_blanks_to_yield = num_blanks_pending
  1312.             elif s.startswith('-?+?'):
  1313.                 yield (_make_line(lines, '?', 0), _make_line(lines, '?', 1), True)
  1314.                 continue
  1315.             elif s.startswith('--++'):
  1316.                 num_blanks_pending -= 1
  1317.                 yield (_make_line(lines, '-', 0), None, True)
  1318.                 continue
  1319.             elif s.startswith('--?+') and s.startswith('--+') or s.startswith('- '):
  1320.                 from_line = _make_line(lines, '-', 0)
  1321.                 to_line = None
  1322.                 num_blanks_to_yield = num_blanks_pending - 1
  1323.                 num_blanks_pending = 0
  1324.             elif s.startswith('-+?'):
  1325.                 yield (_make_line(lines, None, 0), _make_line(lines, '?', 1), True)
  1326.                 continue
  1327.             elif s.startswith('-?+'):
  1328.                 yield (_make_line(lines, '?', 0), _make_line(lines, None, 1), True)
  1329.                 continue
  1330.             elif s.startswith('-'):
  1331.                 num_blanks_pending -= 1
  1332.                 yield (_make_line(lines, '-', 0), None, True)
  1333.                 continue
  1334.             elif s.startswith('+--'):
  1335.                 num_blanks_pending += 1
  1336.                 yield (None, _make_line(lines, '+', 1), True)
  1337.                 continue
  1338.             elif s.startswith('+ ') or s.startswith('+-'):
  1339.                 from_line = None
  1340.                 to_line = _make_line(lines, '+', 1)
  1341.                 num_blanks_to_yield = num_blanks_pending + 1
  1342.                 num_blanks_pending = 0
  1343.             elif s.startswith('+'):
  1344.                 num_blanks_pending += 1
  1345.                 yield (None, _make_line(lines, '+', 1), True)
  1346.                 continue
  1347.             elif s.startswith(' '):
  1348.                 yield (_make_line(lines[:], None, 0), _make_line(lines, None, 1), False)
  1349.                 continue
  1350.             
  1351.             while num_blanks_to_yield < 0:
  1352.                 num_blanks_to_yield += 1
  1353.                 yield (None, ('', '\n'), True)
  1354.             while num_blanks_to_yield > 0:
  1355.                 num_blanks_to_yield -= 1
  1356.                 yield (('', '\n'), None, True)
  1357.             if s.startswith('X'):
  1358.                 raise StopIteration
  1359.                 continue
  1360.             yield (from_line, to_line, True)
  1361.  
  1362.     
  1363.     def _line_pair_iterator():
  1364.         '''Yields from/to lines of text with a change indication.
  1365.  
  1366.         This function is an iterator.  It itself pulls lines from the line
  1367.         iterator.  Its difference from that iterator is that this function
  1368.         always yields a pair of from/to text lines (with the change
  1369.         indication).  If necessary it will collect single from/to lines
  1370.         until it has a matching pair from/to pair to yield.
  1371.  
  1372.         Note, this function is purposefully not defined at the module scope so
  1373.         that data it needs from its parent function (within whose context it
  1374.         is defined) does not need to be of module scope.
  1375.         '''
  1376.         line_iterator = _line_iterator()
  1377.         fromlines = []
  1378.         tolines = []
  1379.         while True:
  1380.             while len(fromlines) == 0 or len(tolines) == 0:
  1381.                 (from_line, to_line, found_diff) = line_iterator.next()
  1382.                 if from_line is not None:
  1383.                     fromlines.append((from_line, found_diff))
  1384.                 
  1385.                 if to_line is not None:
  1386.                     tolines.append((to_line, found_diff))
  1387.                     continue
  1388.             (from_line, fromDiff) = fromlines.pop(0)
  1389.             (to_line, to_diff) = tolines.pop(0)
  1390.             if not fromDiff:
  1391.                 pass
  1392.             yield (from_line, to_line, to_diff)
  1393.  
  1394.     line_pair_iterator = _line_pair_iterator()
  1395.     if context is None:
  1396.         while True:
  1397.             yield line_pair_iterator.next()
  1398.     else:
  1399.         context += 1
  1400.         lines_to_write = 0
  1401.         while True:
  1402.             index = 0
  1403.             contextLines = [
  1404.                 None] * context
  1405.             found_diff = False
  1406.             while found_diff is False:
  1407.                 (from_line, to_line, found_diff) = line_pair_iterator.next()
  1408.                 i = index % context
  1409.                 contextLines[i] = (from_line, to_line, found_diff)
  1410.                 index += 1
  1411.             if index > context:
  1412.                 yield (None, None, None)
  1413.                 lines_to_write = context
  1414.             else:
  1415.                 lines_to_write = index
  1416.                 index = 0
  1417.             while lines_to_write:
  1418.                 i = index % context
  1419.                 index += 1
  1420.                 yield contextLines[i]
  1421.                 lines_to_write -= 1
  1422.             lines_to_write = context - 1
  1423.             while lines_to_write:
  1424.                 (from_line, to_line, found_diff) = line_pair_iterator.next()
  1425.                 if found_diff:
  1426.                     lines_to_write = context - 1
  1427.                 else:
  1428.                     lines_to_write -= 1
  1429.                 yield (from_line, to_line, found_diff)
  1430.  
  1431. _file_template = '\n<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"\n          "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">\n\n<html>\n\n<head>\n    <meta http-equiv="Content-Type"\n          content="text/html; charset=ISO-8859-1" />\n    <title></title>\n    <style type="text/css">%(styles)s\n    </style>\n</head>\n\n<body>\n    %(table)s%(legend)s\n</body>\n\n</html>'
  1432. _styles = '\n        table.diff {font-family:Courier; border:medium;}\n        .diff_header {background-color:#e0e0e0}\n        td.diff_header {text-align:right}\n        .diff_next {background-color:#c0c0c0}\n        .diff_add {background-color:#aaffaa}\n        .diff_chg {background-color:#ffff77}\n        .diff_sub {background-color:#ffaaaa}'
  1433. _table_template = '\n    <table class="diff" id="difflib_chg_%(prefix)s_top"\n           cellspacing="0" cellpadding="0" rules="groups" >\n        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>\n        <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>\n        %(header_row)s\n        <tbody>\n%(data_rows)s        </tbody>\n    </table>'
  1434. _legend = '\n    <table class="diff" summary="Legends">\n        <tr> <th colspan="2"> Legends </th> </tr>\n        <tr> <td> <table border="" summary="Colors">\n                      <tr><th> Colors </th> </tr>\n                      <tr><td class="diff_add"> Added </td></tr>\n                      <tr><td class="diff_chg">Changed</td> </tr>\n                      <tr><td class="diff_sub">Deleted</td> </tr>\n                  </table></td>\n             <td> <table border="" summary="Links">\n                      <tr><th colspan="2"> Links </th> </tr>\n                      <tr><td>(f)irst change</td> </tr>\n                      <tr><td>(n)ext change</td> </tr>\n                      <tr><td>(t)op</td> </tr>\n                  </table></td> </tr>\n    </table>'
  1435.  
  1436. class HtmlDiff(object):
  1437.     '''For producing HTML side by side comparison with change highlights.
  1438.  
  1439.     This class can be used to create an HTML table (or a complete HTML file
  1440.     containing the table) showing a side by side, line by line comparison
  1441.     of text with inter-line and intra-line change highlights.  The table can
  1442.     be generated in either full or contextual difference mode.
  1443.  
  1444.     The following methods are provided for HTML generation:
  1445.  
  1446.     make_table -- generates HTML for a single side by side table
  1447.     make_file -- generates complete HTML file with a single side by side table
  1448.  
  1449.     See tools/scripts/diff.py for an example usage of this class.
  1450.     '''
  1451.     _file_template = _file_template
  1452.     _styles = _styles
  1453.     _table_template = _table_template
  1454.     _legend = _legend
  1455.     _default_prefix = 0
  1456.     
  1457.     def __init__(self, tabsize = 8, wrapcolumn = None, linejunk = None, charjunk = IS_CHARACTER_JUNK):
  1458.         '''HtmlDiff instance initializer
  1459.  
  1460.         Arguments:
  1461.         tabsize -- tab stop spacing, defaults to 8.
  1462.         wrapcolumn -- column number where lines are broken and wrapped,
  1463.             defaults to None where lines are not wrapped.
  1464.         linejunk,charjunk -- keyword arguments passed into ndiff() (used to by
  1465.             HtmlDiff() to generate the side by side HTML differences).  See
  1466.             ndiff() documentation for argument default values and descriptions.
  1467.         '''
  1468.         self._tabsize = tabsize
  1469.         self._wrapcolumn = wrapcolumn
  1470.         self._linejunk = linejunk
  1471.         self._charjunk = charjunk
  1472.  
  1473.     
  1474.     def make_file(self, fromlines, tolines, fromdesc = '', todesc = '', context = False, numlines = 5):
  1475.         '''Returns HTML file of side by side comparison with change highlights
  1476.  
  1477.         Arguments:
  1478.         fromlines -- list of "from" lines
  1479.         tolines -- list of "to" lines
  1480.         fromdesc -- "from" file column header string
  1481.         todesc -- "to" file column header string
  1482.         context -- set to True for contextual differences (defaults to False
  1483.             which shows full differences).
  1484.         numlines -- number of context lines.  When context is set True,
  1485.             controls number of lines displayed before and after the change.
  1486.             When context is False, controls the number of lines to place
  1487.             the "next" link anchors before the next change (so click of
  1488.             "next" link jumps to just before the change).
  1489.         '''
  1490.         return self._file_template % dict(styles = self._styles, legend = self._legend, table = self.make_table(fromlines, tolines, fromdesc, todesc, context = context, numlines = numlines))
  1491.  
  1492.     
  1493.     def _tab_newline_replace(self, fromlines, tolines):
  1494.         '''Returns from/to line lists with tabs expanded and newlines removed.
  1495.  
  1496.         Instead of tab characters being replaced by the number of spaces
  1497.         needed to fill in to the next tab stop, this function will fill
  1498.         the space with tab characters.  This is done so that the difference
  1499.         algorithms can identify changes in a file when tabs are replaced by
  1500.         spaces and vice versa.  At the end of the HTML generation, the tab
  1501.         characters will be replaced with a nonbreakable space.
  1502.         '''
  1503.         
  1504.         def expand_tabs(line):
  1505.             line = line.replace(' ', '\x00')
  1506.             line = line.expandtabs(self._tabsize)
  1507.             line = line.replace(' ', '\t')
  1508.             return line.replace('\x00', ' ').rstrip('\n')
  1509.  
  1510.         fromlines = [ expand_tabs(line) for line in fromlines ]
  1511.         tolines = [ expand_tabs(line) for line in tolines ]
  1512.         return (fromlines, tolines)
  1513.  
  1514.     
  1515.     def _split_line(self, data_list, line_num, text):
  1516.         '''Builds list of text lines by splitting text lines at wrap point
  1517.  
  1518.         This function will determine if the input text line needs to be
  1519.         wrapped (split) into separate lines.  If so, the first wrap point
  1520.         will be determined and the first line appended to the output
  1521.         text line list.  This function is used recursively to handle
  1522.         the second part of the split line to further split it.
  1523.         '''
  1524.         if not line_num:
  1525.             data_list.append((line_num, text))
  1526.             return None
  1527.         
  1528.         size = len(text)
  1529.         max = self._wrapcolumn
  1530.         if size <= max or size - text.count('\x00') * 3 <= max:
  1531.             data_list.append((line_num, text))
  1532.             return None
  1533.         
  1534.         i = 0
  1535.         n = 0
  1536.         mark = ''
  1537.         while n < max and i < size:
  1538.             if text[i] == '\x00':
  1539.                 i += 1
  1540.                 mark = text[i]
  1541.                 i += 1
  1542.                 continue
  1543.             if text[i] == '\x01':
  1544.                 i += 1
  1545.                 mark = ''
  1546.                 continue
  1547.             i += 1
  1548.             n += 1
  1549.         line1 = text[:i]
  1550.         line2 = text[i:]
  1551.         if mark:
  1552.             line1 = line1 + '\x01'
  1553.             line2 = '\x00' + mark + line2
  1554.         
  1555.         data_list.append((line_num, line1))
  1556.         self._split_line(data_list, '>', line2)
  1557.  
  1558.     
  1559.     def _line_wrapper(self, diffs):
  1560.         '''Returns iterator that splits (wraps) mdiff text lines'''
  1561.         for fromdata, todata, flag in diffs:
  1562.             if flag is None:
  1563.                 yield (fromdata, todata, flag)
  1564.                 continue
  1565.             
  1566.             (fromline, fromtext) = fromdata
  1567.             (toline, totext) = todata
  1568.             fromlist = []
  1569.             tolist = []
  1570.             self._split_line(fromlist, fromline, fromtext)
  1571.             self._split_line(tolist, toline, totext)
  1572.             while fromlist or tolist:
  1573.                 if fromlist:
  1574.                     fromdata = fromlist.pop(0)
  1575.                 else:
  1576.                     fromdata = ('', ' ')
  1577.                 if tolist:
  1578.                     todata = tolist.pop(0)
  1579.                 else:
  1580.                     todata = ('', ' ')
  1581.                 yield (fromdata, todata, flag)
  1582.         
  1583.  
  1584.     
  1585.     def _collect_lines(self, diffs):
  1586.         '''Collects mdiff output into separate lists
  1587.  
  1588.         Before storing the mdiff from/to data into a list, it is converted
  1589.         into a single line of text with HTML markup.
  1590.         '''
  1591.         fromlist = []
  1592.         tolist = []
  1593.         flaglist = []
  1594.         for fromdata, todata, flag in diffs:
  1595.             
  1596.             try:
  1597.                 fromlist.append(self._format_line(0, flag, *fromdata))
  1598.                 tolist.append(self._format_line(1, flag, *todata))
  1599.             except TypeError:
  1600.                 fromlist.append(None)
  1601.                 tolist.append(None)
  1602.  
  1603.             flaglist.append(flag)
  1604.         
  1605.         return (fromlist, tolist, flaglist)
  1606.  
  1607.     
  1608.     def _format_line(self, side, flag, linenum, text):
  1609.         '''Returns HTML markup of "from" / "to" text lines
  1610.  
  1611.         side -- 0 or 1 indicating "from" or "to" text
  1612.         flag -- indicates if difference on line
  1613.         linenum -- line number (used for line number column)
  1614.         text -- line text to be marked up
  1615.         '''
  1616.         
  1617.         try:
  1618.             linenum = '%d' % linenum
  1619.             id = ' id="%s%s"' % (self._prefix[side], linenum)
  1620.         except TypeError:
  1621.             id = ''
  1622.  
  1623.         text = text.replace('&', '&').replace('>', '>').replace('<', '<')
  1624.         text = text.replace(' ', ' ').rstrip()
  1625.         return '<td class="diff_header"%s>%s</td><td nowrap="nowrap">%s</td>' % (id, linenum, text)
  1626.  
  1627.     
  1628.     def _make_prefix(self):
  1629.         '''Create unique anchor prefixes'''
  1630.         fromprefix = 'from%d_' % HtmlDiff._default_prefix
  1631.         toprefix = 'to%d_' % HtmlDiff._default_prefix
  1632.         HtmlDiff._default_prefix += 1
  1633.         self._prefix = [
  1634.             fromprefix,
  1635.             toprefix]
  1636.  
  1637.     
  1638.     def _convert_flags(self, fromlist, tolist, flaglist, context, numlines):
  1639.         '''Makes list of "next" links'''
  1640.         toprefix = self._prefix[1]
  1641.         next_id = [
  1642.             ''] * len(flaglist)
  1643.         next_href = [
  1644.             ''] * len(flaglist)
  1645.         num_chg = 0
  1646.         in_change = False
  1647.         last = 0
  1648.         for i, flag in enumerate(flaglist):
  1649.             if flag:
  1650.                 if not in_change:
  1651.                     in_change = True
  1652.                     last = i
  1653.                     i = max([
  1654.                         0,
  1655.                         i - numlines])
  1656.                     next_id[i] = ' id="difflib_chg_%s_%d"' % (toprefix, num_chg)
  1657.                     num_chg += 1
  1658.                     next_href[last] = '<a href="#difflib_chg_%s_%d">n</a>' % (toprefix, num_chg)
  1659.                 
  1660.             in_change
  1661.             in_change = False
  1662.         
  1663.         if not flaglist:
  1664.             flaglist = [
  1665.                 False]
  1666.             next_id = [
  1667.                 '']
  1668.             next_href = [
  1669.                 '']
  1670.             last = 0
  1671.             if context:
  1672.                 fromlist = [
  1673.                     '<td></td><td> No Differences Found </td>']
  1674.                 tolist = fromlist
  1675.             else:
  1676.                 fromlist = tolist = [
  1677.                     '<td></td><td> Empty File </td>']
  1678.         
  1679.         if not flaglist[0]:
  1680.             next_href[0] = '<a href="#difflib_chg_%s_0">f</a>' % toprefix
  1681.         
  1682.         next_href[last] = '<a href="#difflib_chg_%s_top">t</a>' % toprefix
  1683.         return (fromlist, tolist, flaglist, next_href, next_id)
  1684.  
  1685.     
  1686.     def make_table(self, fromlines, tolines, fromdesc = '', todesc = '', context = False, numlines = 5):
  1687.         '''Returns HTML table of side by side comparison with change highlights
  1688.  
  1689.         Arguments:
  1690.         fromlines -- list of "from" lines
  1691.         tolines -- list of "to" lines
  1692.         fromdesc -- "from" file column header string
  1693.         todesc -- "to" file column header string
  1694.         context -- set to True for contextual differences (defaults to False
  1695.             which shows full differences).
  1696.         numlines -- number of context lines.  When context is set True,
  1697.             controls number of lines displayed before and after the change.
  1698.             When context is False, controls the number of lines to place
  1699.             the "next" link anchors before the next change (so click of
  1700.             "next" link jumps to just before the change).
  1701.         '''
  1702.         self._make_prefix()
  1703.         (fromlines, tolines) = self._tab_newline_replace(fromlines, tolines)
  1704.         if context:
  1705.             context_lines = numlines
  1706.         else:
  1707.             context_lines = None
  1708.         diffs = _mdiff(fromlines, tolines, context_lines, linejunk = self._linejunk, charjunk = self._charjunk)
  1709.         if self._wrapcolumn:
  1710.             diffs = self._line_wrapper(diffs)
  1711.         
  1712.         (fromlist, tolist, flaglist) = self._collect_lines(diffs)
  1713.         (fromlist, tolist, flaglist, next_href, next_id) = self._convert_flags(fromlist, tolist, flaglist, context, numlines)
  1714.         import cStringIO as cStringIO
  1715.         s = cStringIO.StringIO()
  1716.         fmt = '            <tr><td class="diff_next"%s>%s</td>%s' + '<td class="diff_next">%s</td>%s</tr>\n'
  1717.         for i in range(len(flaglist)):
  1718.             if flaglist[i] is None:
  1719.                 if i > 0:
  1720.                     s.write('        </tbody>        \n        <tbody>\n')
  1721.                 
  1722.             i > 0
  1723.             s.write(fmt % (next_id[i], next_href[i], fromlist[i], next_href[i], tolist[i]))
  1724.         
  1725.         if fromdesc or todesc:
  1726.             header_row = '<thead><tr>%s%s%s%s</tr></thead>' % ('<th class="diff_next"><br /></th>', '<th colspan="2" class="diff_header">%s</th>' % fromdesc, '<th class="diff_next"><br /></th>', '<th colspan="2" class="diff_header">%s</th>' % todesc)
  1727.         else:
  1728.             header_row = ''
  1729.         table = self._table_template % dict(data_rows = s.getvalue(), header_row = header_row, prefix = self._prefix[1])
  1730.         return table.replace('\x00+', '<span class="diff_add">').replace('\x00-', '<span class="diff_sub">').replace('\x00^', '<span class="diff_chg">').replace('\x01', '</span>').replace('\t', ' ')
  1731.  
  1732.  
  1733. del re
  1734.  
  1735. def restore(delta, which):
  1736.     """
  1737.     Generate one of the two sequences that generated a delta.
  1738.  
  1739.     Given a `delta` produced by `Differ.compare()` or `ndiff()`, extract
  1740.     lines originating from file 1 or 2 (parameter `which`), stripping off line
  1741.     prefixes.
  1742.  
  1743.     Examples:
  1744.  
  1745.     >>> diff = ndiff('one\\ntwo\\nthree\\n'.splitlines(1),
  1746.     ...              'ore\\ntree\\nemu\\n'.splitlines(1))
  1747.     >>> diff = list(diff)
  1748.     >>> print ''.join(restore(diff, 1)),
  1749.     one
  1750.     two
  1751.     three
  1752.     >>> print ''.join(restore(diff, 2)),
  1753.     ore
  1754.     tree
  1755.     emu
  1756.     """
  1757.     
  1758.     try:
  1759.         tag = {
  1760.             1: '- ',
  1761.             2: '+ ' }[int(which)]
  1762.     except KeyError:
  1763.         raise ValueError, 'unknown delta choice (must be 1 or 2): %r' % which
  1764.  
  1765.     prefixes = ('  ', tag)
  1766.     for line in delta:
  1767.         if line[:2] in prefixes:
  1768.             yield line[2:]
  1769.             continue
  1770.     
  1771.  
  1772.  
  1773. def _test():
  1774.     import doctest as doctest
  1775.     import difflib as difflib
  1776.     return doctest.testmod(difflib)
  1777.  
  1778. if __name__ == '__main__':
  1779.     _test()
  1780.  
  1781.